package pers.qianyu.month_202101.date_20210115;

import org.junit.*;

import java.util.*;

/**
 * 347. 前 K 个高频元素
 * https://leetcode-cn.com/problems/top-k-frequent-elements/
 *
 * @author mizzle rain
 * @date 2021年1月15日21:14:59
 */
public class TopKFrequent {
    // 计数排序
    public int[] topKFrequent(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) return new int[0];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //System.out.println(map);
        int[] s = new int[len + 1];
        for (Integer key : map.keySet()) {
            Integer value = map.get(key);
            s[value]++;
        }
        //System.out.println(Arrays.toString(s));
        int i = len, t = 0;
        while (t < k) {
            t += s[i--];
        }
        //System.out.println("i = " + i);
        int[] res = new int[k];
        int index = 0;
        for (Integer key : map.keySet()) {
            Integer value = map.get(key);
            if (value > i) {
                res[index++] = key;
            }
        }
        return res;
    }

    @Test
    public void test1() {
        int[] result = new TopKFrequent().topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2);
        System.out.println("result = " + Arrays.toString(result));
    }
}
